1. Field of the Invention
The present invention relates to a packet switch for use in a packet switching system communication network and, more particularly, to a large-scale packet switch having unit switches connected in multi-stages.
2. Description of the Related Art
In a high-speed packet switching system communication network, a large-scale packet switch handling more than several hundreds of lines is realized by connecting a medium- or small-scale packet switches in multi-stages. As an example of a packet switch having such a multi-stage connection structure, a three-stage connection packet switch is shown in FIG. 13.
The packet switch illustrated in FIG. 13 is composed of connected unit switches 1311 and 1312 at the first stage, unit switches 1321 and 1322 at the second stage and unit switches 1331 and 1332 at the third stage. Here, as communication paths, there exist a plurality of paths made by a combination between arbitrary input port and output port.
For accommodating connection-oriented traffic as in ATM (Asynchronous Transfer Mode), selection of a path to be used is made at the setting of a call. On this occasion, for preventing internal blocking (a state where although a free band exists at a final output port, path setting is impossible within the unit switches 1321 and 1322 at the second stage), it is necessary to set paths so as not to cause a deviation in load.
For accommodating connectionless IP traffic, a packet belonging to the same flow should pass through the same path. There therefore arises the need of path selection every time flow starts similarly to the case of connection-oriented traffic.
Then, for either traffic, path selection involving no internal blocking needs centralized control by the entire switch, which results in sacrificing extensibility.
On the other hand, there is a method of preventing internal blocking by, at the outputting of packets from unit switches at the first stage to unit switches at the second stage, evenly distributing the packets to the unit switches at the second stage to macroscopically uniform a load of a unit switch at each second stage. At a multi-stage connection packet switch shown in FIG. 14, switching is conducted according to a destination of a packet at unit switches 1421 and 1422 at the second stage and at a unit switch 1431 at the final stage after returning.
According to such a switching method, however, there occurs a case where packets belonging to the same flow/connection pass through different paths. In a microscopic view, load of each path might vary. As a result, the order of packets at the final stage might be different from that of packets applied to an input port, that is, the original order. For preventing such a situation, a time stamp indicating an input order is assigned at the input port to sequence packets at the unit switch 1431 at the final stage based on the time stamps.
Since this control is local control conducted at the unit switch 1431 at the final stage, distributed control is possible at the unit switch 1431 at each final stage. This is therefore effective when a structure of a packet switch is extended as required.
As a conventional packet switch of this kind using a time stamp, there is, for example, a packet switch disclosed in the literature “A Study of Control Algorithm for Large Scale ATM Switch” (Institute of Electronics, Information and Communication Engineers of Japan, Technical Study Report SSE89-173). According to the art recited in the literature, at the three-stage connection packet switch shown in FIG. 13, a time stamp indicative of a time of packet input is assigned to an input packet at the input ports of the unit switches 1311 and 1312 at the first stage.
Packets assigned time stamps are distributed to the unit switches 1321 and 1322 at the second stage irrespective of their destinations. At the unit switches 1321 and 1322 at the second stage and the unit switches 1331 and 1332 at the third stage, the packets are sent to output ports corresponding to their destinations.
At the output ports of the unit switches 1331 and 1332 at the third stage, the packets are temporarily held for delay. Then, the packets are sequentially output to the output ports, starting with a packet which has passed a time period longer than a predetermined time after the application to the unit switches 1311 and 1312 at the first stage (a maximum delay time required for passing from the unit switches 1311 and 1312 at the first stage to the unit switches 1331 and 1332 at the third stage). The foregoing processing enables packet sequencing.
Another conventional packet switch using a time stamp is, for example, a packet switch recited in Japanese Patent Laying-Open (Kokai) No. heisei 6-6370. According to the technique disclosed in the literature, a unit switch at each first stage first distributes output cells to unit switches at the second stage according to output conditions of cells. Then, a unit switch at the third stage selects, in one clock cycle and for each output line, a cell whose immediately preceding cell is already output from each logic buffer provided corresponding to each unit switch at the first stage one by one, subsequently reads a cell whose time stamp is the oldest from among the selected cells and sends the read cell onto the output line. By the foregoing processing, packets are sequenced.
Conventional packet switches using a time stamp, however, output packets with a delay of a predetermined time in order to sequence packets arriving at unit switches at the final stage as described above. As a result, the switches have a shortcoming that a time required for packet transmission can not be made shorter than a maximum delay time required for a packet to pass from a unit switch at the first stage to a unit switch at the third stage.
In addition, for sequentially outputting a cell whose time stamp is the oldest, it is necessary to compare time stamps of all the cells which can be output to identify a cell having the oldest time stamp, which requires complicated processing.